{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #扁平化多级双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #linked-list #doubly-linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #链表 #双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flatten"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #扁平化多级双向链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。</p>\n",
    "\n",
    "<p>给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]\n",
    "<strong>输出：</strong>[1,2,3,7,8,11,12,9,10,4,5,6]\n",
    "<strong>解释：\n",
    "</strong>\n",
    "输入的多级列表如下图所示：\n",
    "\n",
    "<img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/multilevellinkedlist.png\" style=\"height: 363px; width: 640px;\" />\n",
    "\n",
    "扁平化后的链表如下图：\n",
    "\n",
    "<img src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/12/multilevellinkedlistflattened.png\" style=\"height: 80px; width: 1100px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,null,3]\n",
    "<strong>输出：</strong>[1,3,2]\n",
    "<strong>解释：\n",
    "\n",
    "</strong>输入的多级列表如下图所示：\n",
    "\n",
    "  1---2---NULL\n",
    "  |\n",
    "  3---NULL\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>如何表示测试用例中的多级链表？</strong></p>\n",
    "\n",
    "<p>以 <strong>示例 1</strong> 为例：</p>\n",
    "\n",
    "<pre>\n",
    " 1---2---3---4---5---6--NULL\n",
    "         |\n",
    "         7---8---9---10--NULL\n",
    "             |\n",
    "             11--12--NULL</pre>\n",
    "\n",
    "<p>序列化其中的每一级之后：</p>\n",
    "\n",
    "<pre>\n",
    "[1,2,3,4,5,6,null]\n",
    "[7,8,9,10,null]\n",
    "[11,12,null]\n",
    "</pre>\n",
    "\n",
    "<p>为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。</p>\n",
    "\n",
    "<pre>\n",
    "[1,2,3,4,5,6,null]\n",
    "[null,null,7,8,9,10,null]\n",
    "[null,11,12,null]\n",
    "</pre>\n",
    "\n",
    "<p>合并所有序列化结果，并去除末尾的 null 。</p>\n",
    "\n",
    "<pre>\n",
    "[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点数目不超过 <code>1000</code></li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10^5</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 430&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/\">https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [Qv1Da2](https://leetcode.cn/problems/Qv1Da2/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [Qv1Da2](https://leetcode.cn/problems/Qv1Da2/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]', '[1,2,null,3]', '[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class BSTIterator:\n",
    "\n",
    "    def __init__(self, root: TreeNode):\n",
    "        \n",
    "        # Array containing all the nodes in the sorted order\n",
    "        self.nodes_sorted = []\n",
    "        \n",
    "        # Pointer to the next smallest element in the BST\n",
    "        self.index = -1\n",
    "        \n",
    "        # Call to flatten the input binary search tree\n",
    "        self._inorder(root)\n",
    "        \n",
    "    def _inorder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self._inorder(root.left)\n",
    "        self.nodes_sorted.append(root.val)\n",
    "        self._inorder(root.right)\n",
    "\n",
    "    def next(self) -> int:\n",
    "        \"\"\"\n",
    "        @return the next smallest number\n",
    "        \"\"\"\n",
    "        self.index += 1\n",
    "        return self.nodes_sorted[self.index]\n",
    "\n",
    "    def hasNext(self) -> bool:\n",
    "        \"\"\"\n",
    "        @return whether we have a next smallest number\n",
    "        \"\"\"\n",
    "        return self.index + 1 < len(self.nodes_sorted)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import Tuple\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def myFlatten(self, head: 'Node') -> Tuple['Node']:\n",
    "        if head is None:\n",
    "            return (None, None)\n",
    "\n",
    "        p: 'Node' = head.prev\n",
    "        q: 'Nonde' = head\n",
    "        \n",
    "        while q is not None:\n",
    "            if q.child is not None:\n",
    "                dh, dt = self.myFlatten(q.child)\n",
    "                if q.next is not None:\n",
    "                    q.next.prev = dt\n",
    "                dt.next = q.next\n",
    "                dh.prev = q\n",
    "                q.next = dh\n",
    "                q.child = None\n",
    "                q = dt\n",
    "\n",
    "            p, q = q, q.next\n",
    "\n",
    "        return (head, p)\n",
    "\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        return self.myFlatten(head)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return head\n",
    "        walker = head\n",
    "        stack = []\n",
    "        while walker or stack:\n",
    "            if walker.child != None:\n",
    "                tmp = walker.next\n",
    "                if tmp:\n",
    "                    stack.append(tmp)\n",
    "                \n",
    "                child = walker.child\n",
    "                walker.next = child\n",
    "                child.prev = walker\n",
    "                walker.child = None\n",
    "            else:\n",
    "                if walker.next is None and stack:\n",
    "                    tmp = stack.pop()\n",
    "                    walker.next = tmp\n",
    "                    tmp.prev = walker\n",
    "                    #walker.next.prev = walker\n",
    "            walker = walker.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution(object):\n",
    "    def flatten(self, head):\n",
    "        \"\"\"\n",
    "        :type head: Node\n",
    "        :rtype: Node\n",
    "        \"\"\"\n",
    "        list_res = []\n",
    "        def preOrder(root):\n",
    "            if not root:return None\n",
    "\n",
    "            list_res.append(root.val)\n",
    "            if root.child:\n",
    "                preOrder(root.child)\n",
    "            if root.next:\n",
    "                preOrder(root.next)\n",
    "        preOrder(head)\n",
    "        start = Node(0, None, None, None)\n",
    "        res = start\n",
    "        for each in list_res:\n",
    "            # print(each)\n",
    "            start.next = Node(each, start, None, None)\n",
    "            start = start.next\n",
    "        if res.next:\n",
    "            res.next.prev = None\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        p = res = Node(None, None, None, None)\n",
    "        visited = head and [head]\n",
    "        while visited:\n",
    "            vertex = visited.pop()\n",
    "            if vertex.next:\n",
    "                visited.append(vertex.next)\n",
    "            if vertex.child:\n",
    "                visited.append(vertex.child)\n",
    "            p.next = vertex\n",
    "            p, p.prev, p.child = p.next, p, None\n",
    "        if res.next:\n",
    "            res.next.prev = None\n",
    "        return res.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head == None: return head\n",
    "        p, tail, stack = head, head, []\n",
    "        while p:\n",
    "            tail = p\n",
    "            if p.child:\n",
    "                if p.next: stack.append(p.next)\n",
    "                p.next = p.child\n",
    "                p.child.prev = p\n",
    "                p.child = None     \n",
    "            p = p.next\n",
    "            \n",
    "            if p: continue # p不为空执行上面的逻辑\n",
    "            if len(stack) > 0:\n",
    "                p = stack.pop()\n",
    "                tail.next = p\n",
    "                p.prev = tail\n",
    "                \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = [head]\n",
    "        pre = None\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "                node.child = None\n",
    "            if pre:\n",
    "                node.prev = pre\n",
    "                pre.next = node\n",
    "            pre = node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = []\n",
    "        node = head\n",
    "        while node:\n",
    "            if node.child:\n",
    "                if node.next: # 如果存在 next 部分\n",
    "                    stack.append(node.next) # 就保存\n",
    "                node.child.prev = node # 让 node.child 变成 node.next\n",
    "                node.next = node.child # 同上\n",
    "                node.child = None # 置空 node.child\n",
    "            elif (not node.next) and stack: # 如果走到底没有next了，就把之前保存的 next 拿出来\n",
    "                last_next = stack.pop() # stack里最后一个就是最新的 next\n",
    "                node.next = last_next # 让它，变成当前 node 的 next\n",
    "                last_next.prev = node\n",
    "                \n",
    "            node = node.next\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        stack =[]\n",
    "        pa = head\n",
    "        while pa:\n",
    "            if pa.child:\n",
    "                if pa.next:\n",
    "                    stack.append(pa.next)\n",
    "                pa.child.prev = pa\n",
    "                pa.next = pa.child\n",
    "                pa.child = None\n",
    "                pa = pa.next\n",
    "            else:\n",
    "                if pa.next:\n",
    "                    pa.child = None\n",
    "                    pa.next.prev = pa\n",
    "                    pa = pa.next\n",
    "                if not pa.next:\n",
    "                    pa.child = None\n",
    "                    if stack:\n",
    "                        pa.next = stack.pop()\n",
    "                        pa.next.prev = pa\n",
    "                        pa = pa.next\n",
    "                    else:\n",
    "                        pa = pa.next\n",
    "                        break\n",
    "        return head\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        stack = []\n",
    "        h = Node(0,None,None,None)\n",
    "        h1 = h\n",
    "        stack.append(head)\n",
    "        \n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            \n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "            h.next = node\n",
    "            node.prev,node.next,node.child = h,None,None\n",
    "            h = h.next\n",
    "        if h1.next:\n",
    "            h1.next.prev = None\n",
    "        return h1.next\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        #先从第一级开始遍历\n",
    "        #遇到有子集的节点时，将节点的下一个节点存在栈中\n",
    "        #\n",
    "        if head == None:\n",
    "            return(None)\n",
    "        cur = head\n",
    "        stack = [] #头插\n",
    "        while cur: #不能是cur.next,避免首个节点只有child没有next的情况\n",
    "            while cur.child == None:\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            #检测到有child时：\n",
    "            if cur.child:\n",
    "                stack.insert(0,cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        #切断所有child、收集断点节点后：\n",
    "        while stack:\n",
    "            cur.next = stack.pop(0)\n",
    "            if cur.next:\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "        return(head)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        res=head\n",
    "        tmp=[]\n",
    "        while head:\n",
    "            if head.child!=None:\n",
    "                if head.next!=None:\n",
    "                    tmp.append(head.next)\n",
    "                head.next=head.child\n",
    "                head.child=None\n",
    "                head.next.prev=head\n",
    "            if head.next!=None:\n",
    "                head=head.next\n",
    "            else:\n",
    "                if tmp!=[]:\n",
    "                    tmp1=tmp.pop()\n",
    "                    head.next=tmp1\n",
    "                    tmp1.prev=head\n",
    "                    head=head.next\n",
    "                else:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None \n",
    "        curr = head\n",
    "        while curr:\n",
    "            if curr.child:\n",
    "                n = curr.next \n",
    "                curr.next, curr.child.prev = curr.child, curr \n",
    "                curr.child = None \n",
    "                curr.next = self.flatten(curr.next)\n",
    "                while curr.next:\n",
    "                    curr = curr.next \n",
    "                if n:\n",
    "                    curr.next, n.prev = n, curr \n",
    "            else:\n",
    "                curr = curr.next \n",
    "        return head \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head \n",
    "        \n",
    "        pseudoHead = Node(None, None, head, None)\n",
    "        self.flatten_dfs(pseudoHead, head)\n",
    "\n",
    "        pseudoHead.next.prev = None\n",
    "        return pseudoHead.next\n",
    "\n",
    "    def flatten_dfs(self, pre, curr):\n",
    "        if not curr:\n",
    "            return pre \n",
    "        \n",
    "        curr.prev = pre \n",
    "        pre.next = curr \n",
    "\n",
    "        tempNext = curr.next\n",
    "        tail = self.flatten_dfs(curr, curr.child)  # flatten sub chain \n",
    "        curr.child = None\n",
    "        return self.flatten_dfs(tail, tempNext)   \n",
    "        # connect biconnection between the flattened sub chain and the root's next node "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return head\n",
    "        headpre = Node(None,None,head,None)\n",
    "        self.dfs(headpre,head)\n",
    "        headpre.next.prev = None\n",
    "        return headpre.next\n",
    "    def dfs(self,pre,cur):\n",
    "        if not cur:\n",
    "            return pre\n",
    "        pre.next = cur\n",
    "        cur.prev = pre\n",
    "        tmp = cur.next\n",
    "        tail = self.dfs(cur,cur.child)\n",
    "        cur.child = None\n",
    "        return self.dfs(tail,tmp) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if head.child:\n",
    "                end = dfs(head.child)\n",
    "                if head.next: # 如果有后续节点\n",
    "                    end.next = head.next \n",
    "                    end.next.prev = end \n",
    "                head.next = head.child\n",
    "                head.child.prev = head \n",
    "                head.child = None # 删除子节点\n",
    "            if head.next:\n",
    "                return dfs(head.next)\n",
    "            else:\n",
    "                return head \n",
    "        if not head: \n",
    "            return head \n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        #先从第一级开始遍历\n",
    "        #遇到有子集的节点时，将节点的下一个节点存在栈中\n",
    "        #\n",
    "        if head == None:\n",
    "            return(None)\n",
    "        cur = head\n",
    "        stack = [] #头插\n",
    "        while cur: #不能是cur.next,避免首个节点只有child没有next的情况\n",
    "            while cur.child == None:\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            #检测到有child时：\n",
    "            if cur.child:\n",
    "                stack.insert(0,cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                break\n",
    "        #切断所有child、收集断点节点后：\n",
    "        while stack:\n",
    "            cur.next = stack.pop(0)\n",
    "            if cur.next:  #这里需要判断一下，避免第一级的尾结点存在child节点的情况\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "        return(head)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        s = deque()\n",
    "        cur = head\n",
    "        prev = None\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                if cur.next:\n",
    "                    next = cur.next\n",
    "                    next.prev = None\n",
    "                    s.append(next)\n",
    "                cur.next = cur.child\n",
    "                cur.next.prev = cur\n",
    "                cur.child = None\n",
    "            prev = cur\n",
    "            cur = cur.next\n",
    "        cur = prev\n",
    "        while s:\n",
    "            cur.next = s.pop()\n",
    "            cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        \n",
    "        \n",
    "        find_child = head\n",
    "\n",
    "        while find_child != None:\n",
    "            if find_child.child:\n",
    "                \n",
    "                ptr = find_child\n",
    "\n",
    "                temp = ptr.next\n",
    "                child = ptr.child\n",
    "                child.prev = ptr\n",
    "                \n",
    "                while child.next:\n",
    "                    child = child.next\n",
    "\n",
    "                ptr.next = ptr.child\n",
    "\n",
    "                ptr.child = None\n",
    "                child.next = temp\n",
    "                if temp:\n",
    "                    temp.prev = child\n",
    "            \n",
    "            find_child = find_child.next\n",
    "\n",
    "            head.prev = None\n",
    "        \n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        cur = head\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                start = end = cur.child\n",
    "                while end.next:\n",
    "                    end = end.next\n",
    "                end.next = cur.next\n",
    "                if cur.next:\n",
    "                    cur.next.prev = end\n",
    "                cur.child = None\n",
    "                cur.next = start\n",
    "                start.prev = cur\n",
    "            cur = cur.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self,head:\"Node\")->\"Node\":\n",
    "        def dfs(node:Node)->Node:\n",
    "            cur=node\n",
    "            last=None\n",
    "            while cur:\n",
    "                next=cur.next\n",
    "                if cur.child:\n",
    "                    childLast=dfs(cur.child)\n",
    "                    next=cur.next\n",
    "                    cur.next=cur.child\n",
    "                    cur.child.prev=cur\n",
    "                    cur.child=None\n",
    "                    if next:\n",
    "                        next.prev=childLast\n",
    "                        childLast.next=next\n",
    "                    last=childLast\n",
    "                else:\n",
    "                    last=cur\n",
    "                cur=next\n",
    "            return last\n",
    "        if head==None:return None\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def dfs(head):\n",
    "            pre = None\n",
    "            while head:\n",
    "                if not head.child:\n",
    "                    pre = head\n",
    "                    head = head.next\n",
    "                else:\n",
    "                    nxt = head.next\n",
    "                    childLast = dfs(head.child)\n",
    "                    head.next = head.child\n",
    "                    head.child.prev = head\n",
    "                    head.child = None\n",
    "                    childLast.next = nxt\n",
    "                    if nxt:\n",
    "                        nxt.prev = childLast\n",
    "                    pre = childLast\n",
    "                    head = nxt\n",
    "            return pre\n",
    "\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        def link_child(node_father:'Node', node_child:'Node'):\n",
    "            if not node_child:\n",
    "                return node_father\n",
    "            node_father.next = node_child\n",
    "            node_child.prev = node_father\n",
    "\n",
    "            next_child = node_child.next\n",
    "            tail = link_child(node_child, node_child.child)\n",
    "\n",
    "            node_child.child = None\n",
    "\n",
    "            return link_child(tail, next_child)\n",
    "            \n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        tmp = Node(-1, None, None, None)\n",
    "        tmp.next = head\n",
    "        \n",
    "        link_child(tmp, head)\n",
    "        tmp.next.prev = None\n",
    "        \n",
    "        return tmp.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        s = head\n",
    "        while s:\n",
    "            if s.child:\n",
    "                nex = s.next\n",
    "                cur = s.child\n",
    "\n",
    "                s.next = cur\n",
    "                s.child = None\n",
    "                cur.prev = s\n",
    "                while cur.next:\n",
    "                    cur = cur.next\n",
    "                if nex:\n",
    "                    nex .prev = cur\n",
    "                cur.next = nex\n",
    "            s = s.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        visitor = head\n",
    "        while visitor != None:\n",
    "            if visitor.child == None:\n",
    "                visitor = visitor.next\n",
    "                continue\n",
    "            childvisitor = visitor.child\n",
    "            while childvisitor.next != None:\n",
    "                childvisitor = childvisitor.next\n",
    "            childvisitor.next = visitor.next\n",
    "            if visitor.next != None:\n",
    "                visitor.next.prev = childvisitor\n",
    "            visitor.next = visitor.child\n",
    "            visitor.child.prev = visitor\n",
    "            visitor.child = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head:\n",
    "            return head\n",
    "        self.dfs(head)\n",
    "        return head\n",
    "    \n",
    "    def dfs(self, node):\n",
    "        while node.next and not node.child:\n",
    "            node = node.next\n",
    "        \n",
    "        tail = None\n",
    "        if node.child:\n",
    "            tail = self.dfs(node.child)\n",
    "\n",
    "            temp = node.next\n",
    "            node.next = node.child\n",
    "            node.child.prev = node\n",
    "            node.child = None\n",
    "            tail.next = temp\n",
    "            if temp:\n",
    "                temp.prev = tail\n",
    "            return self.dfs(tail)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: \"Node\") -> \"Node\":\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node\n",
    "            # 记录链表的最后一个节点\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                # 如果有子节点，那么首先处理子节点\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    \n",
    "                    nxt = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    # 如果 nxt 不为空，就将 last 与 nxt 相连\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "\n",
    "                    # 将 child 置为空\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return None, None\n",
    "            \n",
    "            head = tail = node\n",
    "            child = node.child\n",
    "            nex = node.next\n",
    "            node.next = None\n",
    "            node.child = None\n",
    "            \n",
    "            son_head, son_tail = dfs(child)\n",
    "            if son_head:\n",
    "                head.next = son_head\n",
    "                head.next.prev = head\n",
    "                tail = son_tail\n",
    "\n",
    "            post_head, post_tail = dfs(nex)\n",
    "            if post_head:\n",
    "                tail.next = post_head\n",
    "                tail.next.prev = tail\n",
    "                tail = post_tail\n",
    "            return head, tail\n",
    "\n",
    "        return dfs(head)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        curr = root\n",
    "        while curr:\n",
    "            if curr.left != None:\n",
    "                prev = curr.left\n",
    "                while prev.right:\n",
    "                    prev = prev.right\n",
    "                prev.right = curr.right\n",
    "                curr.right = curr.left\n",
    "                curr.left = None\n",
    "            curr = curr.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "        \n",
    "\n",
    "        if root.left:\n",
    "            temp=root.right\n",
    "            root.right=root.left\n",
    "            root.left=None\n",
    "\n",
    "            right=root.right\n",
    "\n",
    "            while right and right.right:\n",
    "                right=right.right\n",
    "\n",
    "            right.right=temp\n",
    "        \n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def _firstorderTraversal(_root, out):\n",
    "            out.append(_root.val)\n",
    "            if _root.left:\n",
    "                out = _firstorderTraversal(_root.left, out)\n",
    "            if _root.right:\n",
    "                out = _firstorderTraversal(_root.right, out)\n",
    "            return out\n",
    "\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        out = _firstorderTraversal(root, [])\n",
    "        print(out)\n",
    "\n",
    "        head = root\n",
    "        for each in out[1:]:\n",
    "            head.right = TreeNode(each)\n",
    "            head.left = None\n",
    "            head = head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        def deep_search(node):\n",
    "            left_c = node.left\n",
    "            right_c = node.right\n",
    "            last_c = node\n",
    "\n",
    "            if left_c is not None:\n",
    "                node.right = left_c\n",
    "                node.left = None\n",
    "                last_c = deep_search(left_c)\n",
    "            if right_c is not None:\n",
    "                last_c.right = right_c\n",
    "                last_c = deep_search(right_c)\n",
    "            return last_c\n",
    "        if root is not None:\n",
    "            deep_search(root)\n",
    "\n",
    "        \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        cur = root\n",
    "        while cur:\n",
    "            if cur.left:\n",
    "                tmp = cur.left\n",
    "                while tmp.right:\n",
    "                    tmp = tmp.right\n",
    "                tmp.right = cur.right\n",
    "                cur.right = cur.left\n",
    "                cur.left = None\n",
    "            cur = cur.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        replace(root)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        replace(root)\n",
    "\n",
    "\n",
    "\n",
    "def replace(node:TreeNode):\n",
    "    if not node:\n",
    "        return\n",
    "    temp = node.right\n",
    "\n",
    "    if node.left != None:\n",
    "        node.right = node.left\n",
    "\n",
    "        p = node.left\n",
    "\n",
    "        if temp:\n",
    "            while p.right != None:\n",
    "                p = p.right\n",
    "            p.right = temp\n",
    "    else:\n",
    "        if temp:\n",
    "            node.right = temp\n",
    "\n",
    "    node.left = None\n",
    "\n",
    "    replace(node.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        if root == None:\n",
    "            return\n",
    "        \n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "        \n",
    "        temp = root.right\n",
    "        root.right = root.left\n",
    "        root.left = None\n",
    "        tail = root\n",
    "        while(tail.right != None):\n",
    "            print (tail.val)\n",
    "            tail = tail.right\n",
    "        tail.right = temp\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: void Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if root is None: return \n",
    "        \n",
    "        def helper(bt):\n",
    "            left = bt.left\n",
    "            right = bt.right\n",
    "            if left:\n",
    "                tmp = left\n",
    "                while tmp.right:\n",
    "                    tmp = tmp.right\n",
    "                tmp.right = right\n",
    "            else:\n",
    "                left = right\n",
    "            bt.left = None\n",
    "            bt.right = left\n",
    "            if bt.left:\n",
    "                helper(bt.left)\n",
    "            if bt.right:\n",
    "                helper(bt.right)\n",
    "                \n",
    "        helper(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def flatten(self, root: TreeNode) -> None:\r\n",
    "        \"\"\"\r\n",
    "        Do not return anything, modify root in-place instead.\r\n",
    "        \"\"\"\r\n",
    "\r\n",
    "        cur=root\r\n",
    "\r\n",
    "        while cur:\r\n",
    "            if cur.left:\r\n",
    "                p=cur.left\r\n",
    "                while p.right:\r\n",
    "                    p=p.right\r\n",
    "                p.right=cur.right\r\n",
    "                cur.right=cur.left\r\n",
    "                cur.left=None\r\n",
    "\r\n",
    "            cur=cur.right\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    ptr = None\n",
    "    def _flatten(self, root):\n",
    "        if root == None:\n",
    "            self.ptr.right = root\n",
    "            return\n",
    "        left_node = root.left\n",
    "        right_node = root.right\n",
    "        self.ptr.right = root\n",
    "        self.ptr = self.ptr.right\n",
    "        root.left = None\n",
    "        root.right = None\n",
    "        self._flatten(left_node)\n",
    "        self._flatten(right_node)\n",
    "\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        res = TreeNode(0)\n",
    "        self.ptr = res\n",
    "        self._flatten(root)\n",
    "        return res.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "        res = []\n",
    "        def preOrder(node):\n",
    "            if node:\n",
    "                res.append(node)\n",
    "            if node.left:\n",
    "                preOrder(node.left)\n",
    "            if node.right:\n",
    "                preOrder(node.right)\n",
    "        preOrder(root)\n",
    "        for i in range(len(res)-1):\n",
    "            res[i].left = None\n",
    "            res[i].right = res[i+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if not root.left:\n",
    "                root = root.right\n",
    "            # 找左子树的最右节点\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                # 将原来的右子树接到左子树的最右边节点\n",
    "                pre.right = root.right\n",
    "                # 将左子树插入到右子树的地方\n",
    "                root.right, root.left = root.left, None\n",
    "                # 考虑下一个节点\n",
    "                root = root.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        stack = [root]\n",
    "        prev = None\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if prev:\n",
    "                prev.right = node\n",
    "                prev.left = None\n",
    "            if node:\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.left)\n",
    "                prev = node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        # check\n",
    "        if not root: return root\n",
    "\n",
    "        # init\n",
    "        stack = [root]\n",
    "        \n",
    "        # loop\n",
    "        while len(stack):\n",
    "            curr = stack.pop()\n",
    "            if curr:\n",
    "                node_l, node_r = curr.left, curr.right\n",
    "                if node_r:  stack.append(node_r)\n",
    "                if node_l:  stack.append(node_l)\n",
    "                curr.right = stack[-1] if len(stack) else None\n",
    "                curr.left = None\n",
    "        return root "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        curr = root\n",
    "        while curr:\n",
    "            if curr.left:\n",
    "                p = curr.left\n",
    "                while p.right:\n",
    "                    p = p.right\n",
    "                p.right = curr.right\n",
    "                curr.right = curr.left\n",
    "                curr.left = None\n",
    "            curr = curr.right\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.helper(root)\n",
    "        \n",
    "\n",
    "    def helper(self, root):\n",
    "        while root:\n",
    "            if not root.left:\n",
    "                root = root.right\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                pre.right = root.right\n",
    "                root.right = root.left\n",
    "                root.left = None\n",
    "                root = root.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return\n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "        left = root.left\n",
    "        right = root.right\n",
    "\n",
    "        root.left = None\n",
    "        root.right = left\n",
    "        while root.right:\n",
    "            root = root.right\n",
    "        root.right = right\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if root.left is None:\n",
    "                root = root.right\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right is not None:\n",
    "                    pre = pre.right\n",
    "                pre.right = root.right\n",
    "                root.right = root.left\n",
    "                root.left = None\n",
    "                root = root.right\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root:\n",
    "            if not root.left:\n",
    "                root = root.right\n",
    "            else:\n",
    "                pre = root.left\n",
    "                while pre.right:\n",
    "                    pre = pre.right\n",
    "                pre.right = root.right\n",
    "                root.right = root.left\n",
    "                root.left = None\n",
    "                root = root.right\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.to_link(root)\n",
    "\n",
    "    def to_link(self, root):\n",
    "        if root.left is None and root.right is None:\n",
    "            return root\n",
    "\n",
    "        end = root\n",
    "        right = root.right\n",
    "        if root.left is not None:\n",
    "            end = self.to_link(root.left)\n",
    "            root.right = root.left\n",
    "            root.left = None\n",
    "\n",
    "        if right is not None:\n",
    "            end.right = right\n",
    "            end = self.to_link(right)\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def helper(node):\n",
    "            if not node:\n",
    "                return None, None\n",
    "            if not node.left and not node.right:\n",
    "                return node, node\n",
    "            left_head, left_tail = helper(node.left)\n",
    "            right_head, right_tail = helper(node.right)\n",
    "            if left_head:\n",
    "                node.right = left_head\n",
    "                node.left = None\n",
    "                left_tail.right = right_head\n",
    "            else:\n",
    "                node.right = right_head\n",
    "            if right_tail:\n",
    "                return node, right_tail\n",
    "            else: \n",
    "                return node, left_tail \n",
    "\n",
    "        helper(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            res.append(root)\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        for i in range(len(res) - 1):\n",
    "            res[i].right = res[i + 1]\n",
    "            res[i].left = None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def traverse(self, node):\n",
    "        if node is None:\n",
    "            return\n",
    "        \n",
    "        left = self.traverse(node.left)\n",
    "        right = self.traverse(node.right)\n",
    "\n",
    "        if left is None:\n",
    "            left = right\n",
    "        else:\n",
    "            p = left\n",
    "            while p.right:\n",
    "                p=p.right\n",
    "            p.right=right\n",
    "\n",
    "        node.right=left\n",
    "        node.left=None\n",
    "        return node\n",
    "\n",
    "\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        pass\n",
    "        self.traverse(root)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:return None\n",
    "        tmp = root.right\n",
    "        root.right = None\n",
    "        if root.left:\n",
    "            root.right = self.flatten(root.left)\n",
    "            root.left = None\n",
    "        cur = root\n",
    "        while cur.right:\n",
    "            cur = cur.right\n",
    "        cur.right = self.flatten(tmp)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def preorder(self, root, ans):\n",
    "        if root:\n",
    "            ans.append(root)\n",
    "            self.preorder(root.left, ans)\n",
    "            self.preorder(root.right, ans)\n",
    "\n",
    "    def recursion(self, root):\n",
    "        ans = []\n",
    "        self.preorder(root, ans)\n",
    "        for i in range(len(ans)-1):\n",
    "            curnode, nextnode = ans[i], ans[i+1]\n",
    "            curnode.right = nextnode\n",
    "            curnode.left = None\n",
    "    \n",
    "    def iteratin(self, root):\n",
    "        if root:\n",
    "            rootlist = []\n",
    "            sta = [root]\n",
    "            while sta:\n",
    "                curnode = sta.pop()\n",
    "                rootlist.append(curnode)\n",
    "                if curnode.right:\n",
    "                    sta.append(curnode.right)\n",
    "                if curnode.left:\n",
    "                    sta.append(curnode.left)\n",
    "                \n",
    "            for i in range(len(rootlist)-1):\n",
    "                curnode, nextnode = rootlist[i], rootlist[i+1]\n",
    "                curnode.right = nextnode\n",
    "                curnode.left = None\n",
    "    def prenode(self, root):\n",
    "        if root:\n",
    "            tmp = root\n",
    "            while tmp:\n",
    "                while tmp.left:\n",
    "                    pre = tmp.left\n",
    "                    while pre.right:\n",
    "                        pre = pre.right\n",
    "                    pre.right = tmp.right\n",
    "                    tmp.right = tmp.left\n",
    "                    tmp.left = None\n",
    "                tmp = tmp.right \n",
    "    def preorderplus(self, root):\n",
    "        if root:\n",
    "            sta = [root]\n",
    "            pre = None\n",
    "            while sta:\n",
    "                cur = sta.pop()\n",
    "                if pre:\n",
    "                    pre.right = cur\n",
    "                    pre.left = None\n",
    "                if cur.right:\n",
    "                    sta.append(cur.right)\n",
    "                if cur.left:\n",
    "                    sta.append(cur.left)\n",
    "                pre = cur\n",
    "\n",
    "\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.recursion(root)\n",
    "        # self.iteratin(root)\n",
    "        # self.prenode(root)\n",
    "        # self.preorderplus(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        while root and root.left is None:\n",
    "            root = root.right\n",
    "        if root is None:\n",
    "            return\n",
    "\n",
    "        right = root.right\n",
    "        left = root.left\n",
    "        cur = left\n",
    "        while cur.right:\n",
    "            cur = cur.right\n",
    "        cur.right = right\n",
    "        root.right = left\n",
    "        root.left = None\n",
    "        self.flatten(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        lst = []\n",
    "        self.first_order(root, lst)\n",
    "\n",
    "        size = len(lst)\n",
    "        for i in range(1, size):\n",
    "            prev, cur = lst[i-1], lst[i]\n",
    "            prev.right = cur\n",
    "            prev.left = None\n",
    "\n",
    "\n",
    "\n",
    "    def first_order(self, root, lst):\n",
    "        if root == None:\n",
    "            return \n",
    "        \n",
    "        lst.append(root)\n",
    "        \n",
    "        self.first_order(root.left, lst)\n",
    "        self.first_order(root.right, lst)\n",
    "        \n",
    "        return lst\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, root: TreeNode) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return None\n",
    "        self.flatten(root.left)\n",
    "        self.flatten(root.right)\n",
    "\n",
    "        if root.left:\n",
    "            temp = root.right\n",
    "            root.right =  root.left\n",
    "            root.left = None\n",
    "            while root.right:\n",
    "                root=root.right\n",
    "            root.right=temp\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def traverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            right1 = traverse(root.left)\n",
    "            right2 = traverse(root.right)\n",
    "            root.right =right1\n",
    "            root.left = None\n",
    "            p = root\n",
    "            while p.right:\n",
    "                p =p.right\n",
    "            p.right = right2\n",
    "            return root\n",
    "        root = traverse(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    last_node = None\n",
    "\n",
    "    def flatten(self, root: Optional[TreeNode]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify root in-place instead.\n",
    "        \"\"\"\n",
    "        self.last_node = None\n",
    "        def helper(node: TreeNode):\n",
    "            if not node:\n",
    "                return\n",
    "            helper(node.right)\n",
    "            helper(node.left)\n",
    "            node.right = self.last_node\n",
    "            node.left = None\n",
    "            self.last_node = node\n",
    "\n",
    "        helper(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        pre = Node(0,None,None,None)\n",
    "        stack = [head]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            cur.prev = pre\n",
    "            pre.next = cur\n",
    "            pre = cur\n",
    "            if cur.next:\n",
    "                stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        pre, now, stack = None, head, []\n",
    "        while now or stack:\n",
    "            if now is None:\n",
    "                now = stack.pop()\n",
    "                pre.next = now\n",
    "                now.prev = pre\n",
    "            pre = now\n",
    "            if now.child:\n",
    "                if now.next:\n",
    "                    stack.append(now.next)\n",
    "                now.next = now.child\n",
    "                now.child = None\n",
    "                now = now.next\n",
    "                now.prev = pre\n",
    "            else:\n",
    "                now = now.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        stack = [head]\n",
    "        pre = None\n",
    "        while stack:\n",
    "            p = stack.pop()\n",
    "            if p and pre:\n",
    "                pre.next = p\n",
    "                p.prev = pre\n",
    "            while p:\n",
    "                if p.child:\n",
    "                    stack.append(p.next)\n",
    "                    p.next = p.child\n",
    "                    p.child = None\n",
    "                    p.next.prev = p\n",
    "                pre = p\n",
    "                p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        pre = Node()\n",
    "        q = [head]\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            cur.prev = pre\n",
    "            pre.next = cur\n",
    "            pre = cur\n",
    "            if cur.next:q.append(cur.next)\n",
    "            if cur.child:\n",
    "                q.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        curr = head \n",
    "        while curr:\n",
    "            if curr.child:\n",
    "                nxt = curr.next \n",
    "                child = curr.child\n",
    "\n",
    "                curr.next = child \n",
    "                curr.child = None \n",
    "                child.prev = curr \n",
    "\n",
    "                while child.next:\n",
    "                    child = child.next \n",
    "                \n",
    "                if nxt:\n",
    "                    nxt.prev = child \n",
    "                child.next = nxt \n",
    "            \n",
    "            curr = curr.next \n",
    "        \n",
    "        return head \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "# class Solution:\n",
    "#     def flatten(self, head: 'Node') -> 'Node':\n",
    "#         if not head: return head\n",
    "#         def dfs(pre, cur):\n",
    "#             if cur == None: return pre\n",
    "#             pre.next = cur\n",
    "#             cur.prev = pre\n",
    "#             nxt = cur.next\n",
    "#             node = dfs(cur, cur.child)\n",
    "#             cur.child = None\n",
    "#             return dfs(node, nxt)\n",
    "#         dummy = Node(0, None, None, None)\n",
    "#         dfs(dummy, head)\n",
    "#         dummy.next.prev = None\n",
    "#         return dummy.next\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head: return head\n",
    "        dummy = Node(0, None, None, None)\n",
    "        pre = dummy\n",
    "        stack = [head]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            node.prev = pre\n",
    "            pre.next = node\n",
    "            if node.next:\n",
    "                stack.append(node.next)\n",
    "            if node.child:\n",
    "                stack.append(node.child)\n",
    "                node.child = None\n",
    "            pre = node\n",
    "        dummy.next.prev = None\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        stack = [head]\n",
    "        pre = Node()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:\n",
    "                stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        ptr=head\n",
    "        list=[]\n",
    "        dummmy=Node(0,None,None,None)\n",
    "        ptrlast=dummmy\n",
    "        while 1:\n",
    "            if ptr==None:\n",
    "                if len(list)==0:\n",
    "                    if dummmy.next==None:\n",
    "                        return None\n",
    "                    dummmy.next.prev=None\n",
    "                    return head\n",
    "                else:\n",
    "                    ptr=list.pop()\n",
    "            else:\n",
    "                ptrlast.next=ptr\n",
    "                ptr.prev=ptrlast\n",
    "                ptrlast=ptr\n",
    "                if ptr.child!=None:\n",
    "                    if ptr.next!=None:\n",
    "                        list.append(ptr.next)\n",
    "                    ptr=ptr.child\n",
    "                    ptrlast.child=None\n",
    "                else:\n",
    "                    ptr=ptr.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        # if head == None: # 异常处理很重要!\n",
    "        #     return head\n",
    "        # def dfs(pre, cur) -> 'Node':\n",
    "        #     if cur == None:\n",
    "        #         return pre\n",
    "        #     pre.next = cur\n",
    "        #     cur.prev = pre\n",
    "        #     nxt = cur.next\n",
    "        #     tail = dfs(cur, cur.child)\n",
    "        #     cur.child = None\n",
    "        #     return dfs(tail, nxt)\n",
    "        # dummy = Node(0, None, None, None)\n",
    "        # dfs(dummy, head)\n",
    "        # dummy.next.prev = None\n",
    "        # return dummy.next\n",
    "        if head == None:\n",
    "            return head\n",
    "        pre = dummy = Node()\n",
    "        stack = [head]\n",
    "        while stack:\n",
    "            x = stack.pop()\n",
    "            pre.next = x\n",
    "            x.prev = pre\n",
    "            if x.next:\n",
    "                stack.append(x.next)\n",
    "            if x.child:\n",
    "                stack.append(x.child)\n",
    "                x.child = None\n",
    "            pre = x\n",
    "        dummy.next.prev = None\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        stack = [head]\n",
    "        pre = Node()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:\n",
    "                stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        pre = ans = Node(0,None,None,None)\n",
    "        stack = [head]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pre.next = cur \n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        q = [head]\n",
    "        pre = Node()\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:q.append(cur.next)\n",
    "            if cur.child:\n",
    "                q.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        def connect(p, q):\n",
    "            while q.next:\n",
    "                q = q.next\n",
    "            q.next = p.next\n",
    "            p.next = p.child\n",
    "            p.child = None\n",
    "            p.next.prev = p\n",
    "            if q.next:\n",
    "                q.next.prev = q\n",
    "            return p\n",
    "        \n",
    "        h = head\n",
    "        while head:\n",
    "            if head.child != None:\n",
    "                head = connect(head, head.child)\n",
    "            head = head.next\n",
    "        \n",
    "        return h\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        stack = [head]\n",
    "        pre = Node()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:\n",
    "                stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "\n",
    "        stack = [head]\n",
    "        pre = Node()\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next :\n",
    "                stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head == None:\n",
    "            return head\n",
    "\n",
    "        dummy = Node(-1, None, None, None)\n",
    "\n",
    "        pre = dummy\n",
    "        stk = [head]\n",
    "\n",
    "        while stk:\n",
    "            x = stk.pop()\n",
    "            \n",
    "            pre.next = x\n",
    "            x.prev = pre\n",
    "\n",
    "            if x.next:\n",
    "                stk.append(x.next)\n",
    "            if x.child:\n",
    "                stk.append(x.child)\n",
    "                x.child = None\n",
    "            \n",
    "            pre = x\n",
    "        \n",
    "        dummy.next.prev = None\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return\n",
    "        if head.next is None and head.child is None:\n",
    "            return head\n",
    "        record = []\n",
    "        bid_head = head\n",
    "        iter_head = head\n",
    "        while iter_head is not None or len(record) != 0:\n",
    "            # print(iter_head.val)\n",
    "            while iter_head.child is not None:\n",
    "                if iter_head.next is not None:\n",
    "                    record.append(iter_head.next)\n",
    "                iter_head = iter_head.child\n",
    "                bid_head.next = iter_head\n",
    "                iter_head.prev = bid_head\n",
    "                bid_head.child = None\n",
    "                bid_head = bid_head.next\n",
    "            # print(iter_head.val)\n",
    "            while iter_head.next is None and len(record)>0:\n",
    "                iter_head = record[-1]\n",
    "                record.pop()\n",
    "                bid_head.next = iter_head\n",
    "                iter_head.prev = bid_head\n",
    "                bid_head = bid_head.next\n",
    "            iter_head = iter_head.next\n",
    "            if iter_head is not None:\n",
    "                iter_head.prev = bid_head\n",
    "                bid_head = bid_head.next\n",
    "            \n",
    "        if bid_head is None:\n",
    "            return\n",
    "        while bid_head.prev is not None:\n",
    "            bid_head = bid_head.prev\n",
    "        head = bid_head\n",
    "        return head\n",
    "        # head = bid_head\n",
    "        # # return bid_head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        q = [head]\n",
    "        pre = Node()\n",
    "        while q:\n",
    "            cur = q.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:q.append(cur.next)\n",
    "            if cur.child:\n",
    "                q.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        if head:\n",
    "            head,tail = self.flatten_(head)\n",
    "        else:\n",
    "            return head\n",
    "        return head\n",
    "        \n",
    "    def flatten_(self, head: 'Node',depth=0) -> 'Node':\n",
    "        now = head\n",
    "        while(now.next or now.child):\n",
    "            if not now.child:\n",
    "                now = now.next\n",
    "            else:\n",
    "                child_head,child_tail = self.flatten_(now.child,depth+1)\n",
    "                next_node= now.next\n",
    "                if next_node:\n",
    "                    next_node.prev = child_tail\n",
    "                child_tail.next = next_node\n",
    "                now.next = child_head\n",
    "                now.child = None\n",
    "                child_head.prev = now\n",
    "                now = now.next\n",
    "        # self.print_node(head)\n",
    "        return head, now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head: return\n",
    "        mem = []\n",
    "\n",
    "        node = head\n",
    "        while node:\n",
    "            if node.child:\n",
    "                if node.next:\n",
    "                    mem.append(node.next)\n",
    "                node.next, node.child.prev, node.child  = node.child, node, None\n",
    "\n",
    "            if not node.next and mem:\n",
    "                cur = mem.pop()\n",
    "                node.next, cur.prev = cur, node\n",
    "            \n",
    "            node = node.next\n",
    "        \n",
    "        return head\n",
    "            \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:return\n",
    "        stack = [head]\n",
    "        pre = Node(0,None,None,None)\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            pre = cur\n",
    "            if cur.next:\n",
    "                stack.append(cur.next)\n",
    "            if cur.child:\n",
    "                stack.append(cur.child)\n",
    "                cur.child = None\n",
    "        head.prev = None\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def zz(head: 'Optional[Node]') -> ('Optional[Node]', 'Optional[Node]'):\n",
    "            dummy = Node(0, None, head, None)\n",
    "            prev = head\n",
    "            while head:\n",
    "                if head.child:\n",
    "                    ch, ct = zz(head.child)\n",
    "                    head.child = None\n",
    "                    \n",
    "                    ct.next = head.next\n",
    "                    if head.next:\n",
    "                        head.next.prev = ct\n",
    "                        \n",
    "                    head.next = ch\n",
    "                    ch.prev = head\n",
    "                    \n",
    "                    head = ct\n",
    "                prev = head\n",
    "                head = head.next\n",
    "            return dummy.next, prev\n",
    "        return zz(head)[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        s = []\n",
    "        dummy = Node(-1, None, head, None)\n",
    "        pre, curr = dummy, head\n",
    "        while curr:\n",
    "            if curr.child:\n",
    "                if curr.next: s.append(curr.next)\n",
    "                pre = curr\n",
    "                curr = curr.child\n",
    "                pre.next = curr\n",
    "                curr.prev = pre\n",
    "                pre.child = None\n",
    "            elif curr.next:\n",
    "                pre = curr\n",
    "                curr = curr.next\n",
    "            elif s:\n",
    "                pre = curr\n",
    "                curr = s.pop()\n",
    "                pre.next = curr\n",
    "                curr.prev = pre\n",
    "            else:\n",
    "                break\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        dummy = head\n",
    "        while dummy:\n",
    "            if not dummy.child:\n",
    "                dummy = dummy.next\n",
    "            else:\n",
    "                nn = dummy.next\n",
    "                child = dummy.child\n",
    "                dummy.next = child\n",
    "                dummy.child = None\n",
    "                child.prev = dummy\n",
    "                child = self.flatten(child)\n",
    "                while child.next:\n",
    "                    child = child.next\n",
    "                child.next = nn\n",
    "                if nn:\n",
    "                    nn.prev = child\n",
    "                dummy = nn\n",
    "        return head\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node\n",
    "            # 记录链表的最后一个节点\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                # 如果有子节点，那么首先处理子节点\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    nxt = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "                    # 如果 nxt 不为空，就将 last 与 nxt 相连\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "                    # 将 child 置为空\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        cur, stack = head, [None]\n",
    "        pre = None\n",
    "        while cur or stack:\n",
    "            while cur and cur.child == None:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "            if cur:\n",
    "                stack.append(cur.next)\n",
    "                cur.next = cur.child\n",
    "                cur.child.prev = cur\n",
    "                cur.child = None\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if pre and cur:\n",
    "                    pre.next = cur\n",
    "                    cur.prev = pre\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        # 返回扁平化链表\n",
    "\n",
    "\n",
    "        def dfs(node):\n",
    "            # 返回链表最后一个节点\n",
    "            cur = node\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                child = cur.child\n",
    "                if child:\n",
    "                    cur.child = None\n",
    "                    cur.next = child\n",
    "                    child.prev = cur\n",
    "                    end = dfs(child) \n",
    "                    end.next = nxt                   \n",
    "                    cur = end\n",
    "                if nxt:\n",
    "                    nxt.prev = cur\n",
    "                    cur.next = nxt\n",
    "                    cur = nxt\n",
    "                else:\n",
    "                    return cur\n",
    "\n",
    "\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        temp = head\n",
    "        while temp is not None:\n",
    "            temp_next = temp.next\n",
    "            if temp.child is not None:\n",
    "                flatten_child = self.flatten(temp.child)\n",
    "                temp.next = flatten_child\n",
    "                flatten_child.prev = temp\n",
    "                if temp_next is not None:\n",
    "                    last_flatten_child = flatten_child\n",
    "                    while last_flatten_child.next is not None:\n",
    "                        last_flatten_child = last_flatten_child.next\n",
    "                    last_flatten_child.next = temp_next\n",
    "                    temp_next.prev = last_flatten_child\n",
    "                temp.child = None\n",
    "            temp = temp_next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        method = 'leetcode'\n",
    "        if method == 'leetcode':\n",
    "            def dfs(node):\n",
    "                curr = node\n",
    "                last = None\n",
    "                while curr:\n",
    "                    nex = curr.next\n",
    "                    if curr.child:\n",
    "                        child_last = dfs(curr.child)\n",
    "                        nex = curr.next\n",
    "                        curr.next = curr.child\n",
    "                        curr.child.prev = curr\n",
    "                        if nex:\n",
    "                            child_last.next = nex\n",
    "                            nex.prev = child_last\n",
    "                        curr.child = None\n",
    "                        last = child_last\n",
    "                    else:\n",
    "                        last = curr\n",
    "                    curr = nex\n",
    "                return last\n",
    "            dfs(head)\n",
    "            return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def link2list(node: Node, _list: []) -> None:\n",
    "            n = node\n",
    "            while n != None:\n",
    "                _list.append(n)\n",
    "                if n.child != None:\n",
    "                    link2list(n.child, _list)\n",
    "                n = n.next\n",
    "            return\n",
    "        \n",
    "        _list = []\n",
    "        link2list(head, _list)\n",
    "        #print([n.val for n in _list])\n",
    "\n",
    "        last = None\n",
    "        while _list:\n",
    "            node = _list.pop(-1)\n",
    "            node.next = last\n",
    "            if _list:\n",
    "                node.prev = _list[-1]\n",
    "            else:\n",
    "                node.prev = None\n",
    "            node.child = None\n",
    "            last = node\n",
    "        \n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def f(head):\n",
    "            x, tail = head, head\n",
    "            \n",
    "            while x:\n",
    "                nxt = x.next\n",
    "                if not nxt: tail = x\n",
    "                if x.child:\n",
    "                    h, t = f(x.child)\n",
    "                    h.prev = x\n",
    "                    x.next = h\n",
    "                    if nxt: \n",
    "                        nxt.prev = t\n",
    "                    else: tail = t\n",
    "                    t.next = nxt\n",
    "                    x.child = None\n",
    "                x = nxt\n",
    "            return head, tail\n",
    "        return f(head)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(node):\n",
    "            cur = node\n",
    "            last = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    nxt = cur.next\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "            return last\n",
    "        dfs(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        \n",
    "        def recur(node):\n",
    "            cur = node\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                if cur.child:\n",
    "                    child_last = recur(cur.child)\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "            return last\n",
    "        \n",
    "        recur(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def check(head):\n",
    "            #head: start of the linked list\n",
    "            #care for the head.prev by hand!\n",
    "            if not head:\n",
    "                return None\n",
    "            current=head\n",
    "            while current:\n",
    "                if current.child:\n",
    "                    tmp=current.next\n",
    "                    current.child.prev=current\n",
    "                    current.next=current.child\n",
    "                    \n",
    "                    end_node=check(current.child)\n",
    "                    while end_node.next:\n",
    "                        end_node=end_node.next\n",
    "                    end_node.next=tmp\n",
    "                    if tmp:\n",
    "                        tmp.prev=end_node\n",
    "                    current.child=None\n",
    "                    current=tmp\n",
    "                else:\n",
    "                    current=current.next\n",
    "\n",
    "            return head\n",
    "        '''\n",
    "        def get_end(head):\n",
    "            if not head:\n",
    "                return None\n",
    "            current=head\n",
    "            last=current\n",
    "            while current:\n",
    "                last=current\n",
    "                if current.child:\n",
    "                    tmp=current.next\n",
    "                    current.child.prev=current\n",
    "                    current.next=current.child\n",
    "                    #current.child=None\n",
    "                    end_node=get_end(current.child)\n",
    "                    end_node.next=tmp\n",
    "                    if tmp:\n",
    "                        tmp.prev=end_node\n",
    "                    \n",
    "                    current.child=None\n",
    "                    current=tmp\n",
    "                else:\n",
    "                    current=current.next\n",
    "\n",
    "            return last\n",
    "        '''\n",
    "        #print(head.child.child.val)\n",
    "        head=check(head)\n",
    "        return head\n",
    "        #print(head.next.next.next.next.next.next.next.next.next.next.next.prev.prev.prev.prev.prev.prev.prev.prev.prev.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(node):\n",
    "            cur = node\n",
    "            last = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    nex = cur.next\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "            return last\n",
    "        dfs(head)\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def _flatten(head):\n",
    "            tail = head\n",
    "            p = head\n",
    "            while p:\n",
    "                if p.child:\n",
    "                    tail = _flatten(p.child)\n",
    "                    tmp = p.next\n",
    "                    p.next = p.child\n",
    "                    p.child.prev = p\n",
    "                    p.child = None\n",
    "                    tail.next = tmp\n",
    "                    if tmp:\n",
    "                        tmp.prev = tail\n",
    "                else:\n",
    "                    tail = p\n",
    "                    p =p.next\n",
    "            return tail\n",
    "        _ = _flatten(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return head\n",
    "        cur, las = head, head.next\n",
    "        while cur:\n",
    "            if cur.child:\n",
    "                self.flat(cur)\n",
    "            cur = las\n",
    "            if las: las = las.next\n",
    "        return head\n",
    "\n",
    "\n",
    "    def flat(self, node):\n",
    "        las, cil = node.next, node.child\n",
    "        node.next = cil\n",
    "        cil.prev = node\n",
    "        cur = cil.prev\n",
    "        node.child = None\n",
    "        while cil:\n",
    "            if cil.child:\n",
    "                self.flat(cil)\n",
    "            cur = cil\n",
    "            cil = cil.next\n",
    "        cur.next = las\n",
    "        if las:\n",
    "            las.prev = cur\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        \"\"\"\n",
    "        基于dfs的扁平化处理\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(head):\n",
    "            cur, tail = head, None\n",
    "            while cur:\n",
    "                tail = cur\n",
    "                nxt = cur.next\n",
    "                \n",
    "                if cur.child:\n",
    "                    chead, ctail = dfs(cur.child)\n",
    "                    cur.child = None\n",
    "                    # 将扁平后的子链加进来t\n",
    "                    cur.next = chead\n",
    "                    chead.prev = cur\n",
    "                    ctail.next = nxt\n",
    "                    if nxt:\n",
    "                        nxt.prev = ctail\n",
    "                    tail = ctail\n",
    "\n",
    "                cur = nxt\n",
    "\n",
    "            return head, tail\n",
    "        \n",
    "        return dfs(head)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        def recur(node):\n",
    "            cur = node\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                if cur.child:\n",
    "                    child_last = recur(cur.child)\n",
    "\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "                    \n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "            return last\n",
    "        \n",
    "        recur(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "\n",
    "        def what(node):\n",
    "            cur = node\n",
    "            last = node\n",
    "            # if cur.child:\n",
    "            #     l, r = cur.child, what(cur.child)\n",
    "            #     cur.child = None\n",
    "            #     if cur.next: \n",
    "            #         r.next, cur.next.prev = cur.next, r\n",
    "            #     cur.next, l.prev = l, cur\n",
    "            while cur:\n",
    "                if cur.child:\n",
    "                    l, r = cur.child, what(cur.child)\n",
    "                    cur.child = None\n",
    "                    if cur.next: \n",
    "                        r.next, cur.next.prev = cur.next, r\n",
    "                    cur.next, l.prev = l, cur\n",
    "                last = cur\n",
    "                cur = cur.next\n",
    "            return last\n",
    "        what(head)\n",
    "        return head\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def link2list(node: Node, _list: []) -> None:\n",
    "            n = node\n",
    "            while n != None:\n",
    "                _list.append(n)\n",
    "                if n.child != None:\n",
    "                    link2list(n.child, _list)\n",
    "                n = n.next\n",
    "            return\n",
    "        \n",
    "        _list = []\n",
    "        link2list(head, _list)\n",
    "        #print([n.val for n in _list])\n",
    "\n",
    "        last = None\n",
    "        while _list:\n",
    "            node = _list.pop(-1)\n",
    "            node.next = last\n",
    "            if _list:\n",
    "                node.prev = _list[-1]\n",
    "            else:\n",
    "                node.prev = None\n",
    "            node.child = None\n",
    "            last = node\n",
    "        \n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def appendNode(self,val):\n",
    "        self.NewListTail.next = Node(val, self.NewListTail, None, None)\n",
    "        return self.NewListTail.next\n",
    "            \n",
    "    def DFS(self,head):\n",
    "        while head!=None:\n",
    "            self.NewListTail = self.appendNode(head.val)\n",
    "            if head.child:\n",
    "                self.DFS(head.child)\n",
    "            head = head.next\n",
    "\n",
    "    def flatten(self,head:'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        NewListDummy = Node(0, None, None, None)\n",
    "        self.NewListTail = NewListDummy\n",
    "        self.DFS(head)\n",
    "        NewListDummy.next.prev = None\n",
    "        return NewListDummy.next  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "\n",
    "        def dfs(head):\n",
    "            prev, p = head, head\n",
    "            while p:\n",
    "                if p.child is None:\n",
    "                    prev = p\n",
    "                    p = p.next\n",
    "                else:\n",
    "                    tmp = p.next\n",
    "                    child_last = dfs(p.child)\n",
    "\n",
    "                    p.next = p.child\n",
    "                    p.child.prev = p\n",
    "                    p.child = None\n",
    "\n",
    "                    if child_last:\n",
    "                        child_last.next = tmp\n",
    "                    if tmp:\n",
    "                        tmp.prev = child_last\n",
    "\n",
    "                    prev = child_last\n",
    "                    p = tmp\n",
    "\n",
    "            return prev\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        dfs(head)\n",
    "        return head\n",
    "\n",
    "def dfs(node):\n",
    "    if node is None:\n",
    "        return None\n",
    "\n",
    "    cur = node\n",
    "    last = None\n",
    "    while cur is not None:\n",
    "        next = cur.next\n",
    "        if cur.child is not None:\n",
    "            child_last = dfs(cur.child)\n",
    "            cur.next, cur.child.prev, child_last.next = cur.child, cur, cur.next\n",
    "            if child_last.next is not None:\n",
    "                child_last.next.prev = child_last\n",
    "            cur.child = None\n",
    "            last = child_last\n",
    "        else:\n",
    "            last = cur\n",
    "        cur = next\n",
    "\n",
    "    return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: \"Node\") -> \"Node\":\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node\n",
    "            # 记录链表的最后一个节点\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                # 如果有子节点，那么首先处理子节点\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "\n",
    "                    nxt = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    # 如果 nxt 不为空，就将 last 与 nxt 相连\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "\n",
    "                    # 将 child 置为空\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head is None:\n",
    "            return None\n",
    "        def dfs(node):\n",
    "            while node:\n",
    "                while node.next and node.child is None:\n",
    "                    node = node.next\n",
    "                if node.child is None:\n",
    "                    return node\n",
    "                t = node.next\n",
    "                tail = dfs(node.child)\n",
    "                node.next = node.child\n",
    "                node.child = None\n",
    "                node.next.prev = node\n",
    "                tail.next = t\n",
    "                if t:\n",
    "                    t.prev = tail\n",
    "                else:\n",
    "                    return tail\n",
    "                node = t\n",
    "            return node\n",
    "        dfs(head)\n",
    "        return head\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(node):\n",
    "            cur = node\n",
    "            last = None\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "                    if nxt:\n",
    "                        nxt.prev = child_last\n",
    "                        child_last.next = nxt\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: \"Node\") -> \"Node\":\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node\n",
    "            # 记录链表的最后一个节点\n",
    "            last = None\n",
    "\n",
    "            while cur:\n",
    "                nxt = cur.next\n",
    "                # 如果有子节点，那么首先处理子节点\n",
    "                if cur.child:\n",
    "                    child_last = dfs(cur.child)\n",
    "                    \n",
    "                    nxt = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    # 如果 nxt 不为空，就将 last 与 nxt 相连\n",
    "                    if nxt:\n",
    "                        child_last.next = nxt\n",
    "                        nxt.prev = child_last\n",
    "\n",
    "                    # 将 child 置为空\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:\n",
    "                    last = cur\n",
    "                cur = nxt\n",
    "\n",
    "            return last\n",
    "\n",
    "        dfs(head)\n",
    "        return head\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        self.flatten_fun(head)\n",
    "        return head\n",
    "    \n",
    "    def flatten_fun(self, head):\n",
    "        cur, tail = head, None\n",
    "        while cur:\n",
    "            next = cur.next\n",
    "            if cur.child:\n",
    "                child = cur.child\n",
    "                childtail = self.flatten_fun(child)\n",
    "\n",
    "                cur.child = None\n",
    "                cur.next = child\n",
    "                child.prev = cur\n",
    "                childtail.next = next\n",
    "                if next:\n",
    "                    next.prev = childtail\n",
    "                tail = childtail\n",
    "            else:\n",
    "                tail = cur\n",
    "            cur = cur.next\n",
    "        return tail"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "  \n",
    "        \n",
    "        def  flatten_gettail(head:Node):\n",
    "            node = head\n",
    "            tail = None\n",
    "            while node:\n",
    "                next = node.next\n",
    "                if  node.child:\n",
    "                    child = node.child\n",
    "                    child_tail = flatten_gettail(child)\n",
    "\n",
    "                    node.child = None\n",
    "                    node.next = child\n",
    "                    child.prev = node\n",
    "                    child_tail.next = next \n",
    "                    if next:\n",
    "                        next.prev = child_tail\n",
    "                    tail =child_tail\n",
    "                else:\n",
    "                    tail = node\n",
    "\n",
    "                node = next\n",
    "            return tail\n",
    "            \n",
    "        flatten_gettail(head)\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"深度优先搜索dfs\"\"\"\n",
    "\n",
    "    def flatten(self, head: \"Node\") -> \"Node\":\n",
    "        def dfs(node: \"Node\") -> \"Node\":\n",
    "            cur = node  # 每次搜索的初始结点cur\n",
    "            last = None  # 记录待扁平化链表的最后一个节点\n",
    "            while cur:\n",
    "                next_node = cur.next  # next_node是待插入扁平化链表的下一个结点\n",
    "                if cur.child:  # 如果有子节点，那么首先处理子节点\n",
    "                    child_last = dfs(cur.child)\n",
    "\n",
    "                    next_node = cur.next\n",
    "                    # 将 node 与 child 相连\n",
    "                    cur.next = cur.child\n",
    "                    cur.child.prev = cur\n",
    "\n",
    "                    # 如果 next_node 不为空，就将 last 与 next_node 相连\n",
    "                    if next_node:\n",
    "                        child_last.next = next_node\n",
    "                        next_node.prev = child_last\n",
    "\n",
    "                    # 将 child 置为空，防止回溯时造成干扰\n",
    "                    cur.child = None\n",
    "                    last = child_last\n",
    "                else:  # 如果没有子节点，就仅仅更新待扁平化链表的最后结点\n",
    "                    last = cur\n",
    "                cur = next_node\n",
    "\n",
    "            return last\n",
    "\n",
    "        dfs(head)  # 初始从头结点开始搜索\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def sub_flatten(head):\n",
    "            cur = head\n",
    "            ret = cur\n",
    "            while cur:\n",
    "                ret = cur\n",
    "                if cur.child:\n",
    "                    child = cur.child\n",
    "                    tail = sub_flatten(child)\n",
    "                    cur.child = None\n",
    "                    tail.next = cur.next\n",
    "                    if cur.next:\n",
    "                        cur.next.prev = tail\n",
    "                    child.prev = cur\n",
    "                    cur.next = child\n",
    "                    ret = tail\n",
    "                    cur = tail\n",
    "                else:\n",
    "                    cur = cur.next\n",
    "            return ret\n",
    "\n",
    "        sub_flatten(head)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def pri(cur):\n",
    "            print(\"---------\")\n",
    "            while cur:\n",
    "                print(cur.val)\n",
    "                cur = cur.next\n",
    "            print(\"---------\")\n",
    "\n",
    "\n",
    "        def what(chld):\n",
    "            cur = chld\n",
    "            # print(cur.val,\"?\")\n",
    "            if not cur: return\n",
    "            print(head.child)\n",
    "            if cur.child:\n",
    "                print(cur.val)\n",
    "                print(cur.child.val)\n",
    "                l, r = what(cur.child)\n",
    "                cur.child = None\n",
    "                if cur.next: \n",
    "                    r.next, cur.next.prev = cur.next, r\n",
    "                cur.next, l.prev = l, cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "                print(head.child)\n",
    "                if cur.val == 6: pri(head)\n",
    "                print(head.child)\n",
    "                if cur.child:\n",
    "                    print(cur.val)\n",
    "                    print(cur.child.val)\n",
    "                    l, r = what(cur.child)\n",
    "                    cur.child = None\n",
    "                    if cur.next: \n",
    "                        r.next, cur.next.prev = cur.next, r\n",
    "                    cur.next, l.prev = l, cur\n",
    "                print(head.child)\n",
    "            return chld, cur\n",
    "        what(head)\n",
    "        return head\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        self.ans = Node(1, None, None, None)\n",
    "        dumy = self.ans\n",
    "        self.preOrder(head)\n",
    "        if dumy.next:\n",
    "            dumy.next.prev = None\n",
    "        \n",
    "        return dumy.next\n",
    "\n",
    "    \n",
    "    def preOrder(self, node):\n",
    "        if node is not None:\n",
    "            self.ans.next = node \n",
    "            node.prev = self.ans\n",
    "            self.ans = self.ans.next\n",
    "            next = node.next\n",
    "            child = node.child\n",
    "            node.next = None\n",
    "            node.child = None            \n",
    "            self.preOrder(child)\n",
    "            self.preOrder(next)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def link2list(node: Node, _list: []) -> None:\n",
    "            n = node\n",
    "            while n != None:\n",
    "                _list.append(n)\n",
    "                if n.child != None:\n",
    "                    link2list(n.child, _list)\n",
    "                n = n.next\n",
    "            return\n",
    "        \n",
    "        _list = []\n",
    "        link2list(head, _list)\n",
    "        #print([n.val for n in _list])\n",
    "\n",
    "        last = None\n",
    "        while _list:\n",
    "            node = _list.pop(-1)\n",
    "            node.next = last\n",
    "            if _list:\n",
    "                node.prev = _list[-1]\n",
    "            else:\n",
    "                node.prev = None\n",
    "            node.child = None\n",
    "            last = node\n",
    "        \n",
    "        return last"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.next:\n",
    "                node.next.prev = None\n",
    "            tmp = node.next\n",
    "            node.next = None\n",
    "            cur = node\n",
    "\n",
    "            chi = dfs(node.child)\n",
    "            cur.next = chi\n",
    "            if cur.next:\n",
    "                cur.next.prev = cur\n",
    "            while cur.next:\n",
    "                cur = cur.next\n",
    "\n",
    "            post = dfs(tmp)\n",
    "            cur.next = post\n",
    "            if cur.next:\n",
    "                cur.next.prev = cur\n",
    "            node.child = None\n",
    "            return node\n",
    "            \n",
    "        return dfs(head)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head: return head\n",
    "        def dfs(pre, cur):\n",
    "            if cur == None: return pre\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "            nxt = cur.next\n",
    "            node = dfs(cur, cur.child)\n",
    "            cur.child = None\n",
    "            return dfs(node, nxt)\n",
    "        dummy = Node(0, None, None, None)\n",
    "        dfs(dummy, head)\n",
    "        dummy.next.prev = None\n",
    "        return dummy.next     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if head == None:\n",
    "            return head\n",
    "        \n",
    "        dummy = Node(-1, None, None, None)\n",
    "\n",
    "        def dfs(pre: 'Node', cur: 'Node') -> 'Node':\n",
    "            if cur == None:\n",
    "                return pre   \n",
    "\n",
    "            pre.next = cur\n",
    "            cur.prev = pre\n",
    "\n",
    "            nxt_head = cur.next         #相当于4\n",
    "\n",
    "            tail = dfs(cur, cur.child)  #相当于dfs(3, 7)\n",
    "            cur.child = None\n",
    "            \n",
    "            return dfs(tail, nxt_head)  #相当于dfs(12, 4)\n",
    "        \n",
    "        dfs(dummy, head)\n",
    "        dummy.next.prev = None\n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return None, None\n",
    "\n",
    "            if not head.next and not head.child:\n",
    "                return head, head\n",
    "\n",
    "            if not head.child:\n",
    "                _, end = dfs(head.next)\n",
    "                return head, end\n",
    "            \n",
    "            newNext, nexEnd = dfs(head.child)\n",
    "            head.child = None\n",
    "            oldNext = head.next\n",
    "            head.next, newNext.prev = newNext, head\n",
    "            nexEnd.next = oldNext\n",
    "            if oldNext:\n",
    "                oldNext.prev = nexEnd\n",
    "                _, end = dfs(oldNext)\n",
    "                return head, end\n",
    "            else:\n",
    "                return head, nexEnd\n",
    "        \n",
    "        dfs(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return None, None\n",
    "\n",
    "            if not head.next and not head.child:\n",
    "                return head, head\n",
    "\n",
    "            if not head.child:\n",
    "                _, end = dfs(head.next)\n",
    "                return head, end\n",
    "            \n",
    "            newNext, nexEnd = dfs(head.child)\n",
    "            head.child = None\n",
    "            oldNext = head.next\n",
    "            head.next, newNext.prev = newNext, head\n",
    "            nexEnd.next = oldNext\n",
    "            if oldNext:\n",
    "                oldNext.prev = nexEnd\n",
    "                _, end = dfs(oldNext)\n",
    "                return head, end\n",
    "            else:\n",
    "                return head, nexEnd\n",
    "        \n",
    "        dfs(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def f(head):\n",
    "            x, tail = head, head\n",
    "            \n",
    "            while x:\n",
    "                nxt = x.next\n",
    "                if not nxt: tail = x\n",
    "                if x.child:\n",
    "                    h, t = f(x.child)\n",
    "                    h.prev = x\n",
    "                    x.next = h\n",
    "                    if nxt: nxt.prev = t\n",
    "                    else: tail = t\n",
    "                    t.next = nxt\n",
    "                    x.child = None\n",
    "                x = nxt\n",
    "            return head, tail\n",
    "        return f(head)[0]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':\n",
    "        if not head: return None\n",
    "\n",
    "        last = None\n",
    "        def DFS(node):\n",
    "            nonlocal last\n",
    "            if not node:\n",
    "                return\n",
    "            if last:\n",
    "                node.prev.next = None\n",
    "                last.next = node\n",
    "                node.prev = last\n",
    "                last = None\n",
    "            if node.child == None and node.next == None:\n",
    "                last = node\n",
    "            DFS(node.child)\n",
    "            DFS(node.next)\n",
    "        \n",
    "        DFS(head)\n",
    "        ans = head\n",
    "        while head:\n",
    "            if head.child:\n",
    "                head.next = head.child\n",
    "                head.next.prev = head\n",
    "                head.child = None\n",
    "            head = head.next\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    stack = []\n",
    "\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return head\n",
    "            if head.child:\n",
    "                if head.next:\n",
    "                    self.stack.append(head.next)\n",
    "                head.child.prev = head\n",
    "                head.next = dfs(head.child)\n",
    "                head.child = None\n",
    "            elif head.next:\n",
    "                head.next = dfs(head.next)\n",
    "            elif self.stack:\n",
    "                nxt = self.stack.pop()\n",
    "                nxt.prev = head\n",
    "                head.next = dfs(nxt)\n",
    "            return head\n",
    "        \n",
    "        dfs(head)\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return []\n",
    "            return [node.val] + dfs(node.child) + dfs(node.next)\n",
    "\n",
    "        if not head:\n",
    "            return None\n",
    "        res = dfs(head)\n",
    "        dummy = Node(0,None,None,None)\n",
    "        pre = dummy\n",
    "        for i in res:\n",
    "            cur = Node(i, pre, None, None)\n",
    "            pre.next = cur\n",
    "            pre = cur\n",
    "        dummy.next.prev = None\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "# 树的前序遍历\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        nodes = []\n",
    "        def dfs(head):\n",
    "            if not head:\n",
    "                return\n",
    "            nodes.append(head)\n",
    "            dfs(head.child)\n",
    "            dfs(head.next)\n",
    "        dfs(head)\n",
    "        for i in range(len(nodes)-1):\n",
    "            pre = nodes[i]\n",
    "            cur = nodes[i+1]\n",
    "            cur.prev = pre\n",
    "            pre.next = cur\n",
    "            pre.child = None\n",
    "        return head\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, prev, next, child):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def flatten(self, head: 'Node') -> 'Node':\n",
    "        if not head:\n",
    "            return None\n",
    "        p = head\n",
    "        c = self.flatten(p.child)\n",
    "        n = self.flatten(p.next)\n",
    "        p.child = p.next = None\n",
    "        if c:\n",
    "            p.next = c\n",
    "            c.prev = p\n",
    "        while p.next:\n",
    "            p = p.next\n",
    "        if n:\n",
    "            p.next = n\n",
    "            n.prev = p\n",
    "        return head\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
